package grafoS;

/**
 * Gcol is a program to help users to learn a little about graph coloring, in
 * this software, you can learn some coloring algorithms, and add your own
 * algorithm for coloring.You can also learn BFS and DFS search. This tool, also
 * support the .col format from DIMACS (Center for Discrete Mathematics and
 * Theoretical Computer Science), so you can import a big graph and use all the
 * algorithms. Copyright (C) <2015> Clóvis Daniel Souza Silva, Samuel Silva de
 * Souza, Professor Leonardo Sampaio Rocha.
 * 
* This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 * 
* This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 * 
* You should have received a copy of the GNU General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 * 
 * contact: projetoGrafos@gmail.com
 */
/**
 * In this class, insted of we use adjacency matrix, we'll use adjacency List.
 * Why to use Adjacency list ? - to learn how to work with it. We'll use two
 * more classes to complement this one. the Vertice class, where we keep the
 * vertex, and the Adjacencia class, where we link the vertex.
 */
public class GraphList {

    private Vertice v[];
    private Adjacencia a[];
    private int n; // total of vertex.
    private int m; // total of edges.

    public GraphList(int numeroDeVertices) {
        n = numeroDeVertices;
        m = 0;
        a = new Adjacencia[n];
        v = new Vertice[numeroDeVertices];

        for (int i = 0; i < n; i++) {
            v[i] = new Vertice();
            v[i].setNome(i);
        }
    }

    /**
     * Here, we'll link two vertices, for do it, we'll need the vector a, from
     * Adjacencia's class.
     *
     * @param num1 The number of first vertex to be linked
     * @param num2 The number of second vertex to be linked
     */
    public void ligar(int num1, int num2) {
        Vertice v1 = procurarVertice(num1 - 1);
        Vertice v2 = procurarVertice(num2 - 1);
        int aux = procurarIndiceDoVertice(v1);
        if (aux == -1 || v2 == null || v1 == null) {
            System.out.println("Vertice Inexistente");
        } else {
            if (a[aux] == null) {
                a[aux] = new Adjacencia(v1);
                a[aux].setProx(new Adjacencia(v2));
            } else {
                Adjacencia Aux = a[aux];
                while (Aux.getProx() != null && Aux.getProx().getDado().getNome() < num2) {
                    Aux = Aux.getProx();
                }
                if (Aux.getProx() == null) {
                    Aux.setProx(new Adjacencia(v2));
                } else {
                    Adjacencia Elemento = new Adjacencia(v2);
                    Elemento.setProx(Aux.getProx());
                    Aux.setProx(Elemento);
                }
            }
        }
        m++;
    }

    /**
     * Here we search for a vertex v1, if returned -1, it's because the vertex
     * does not exist, else return the aux
     *
     * @param v1 Object Vertice of class Vertice To more information @see
     * Vertice
     * @return the position of vertex in the vertices vector
     */
    public int procurarIndiceDoVertice(Vertice v1) {
        int aux = -1;
        for (int i = 0; i < v.length; i++) {
            if (v[i] != null && v[i].equals(v1)) {
                aux = i;
            }
        }
        return aux;
    }

    /**
     * Here we will seek for a vertex by his name, if the vertex does not exist
     * it will return null
     *
     * @param v1 name of vertex to be sought
     * @return Object Vertice if vertex found
     */
    public Vertice procurarVertice(int v1) {
        Vertice aux = null;
        for (int i = 0; i < v.length; i++) {
            if (v[i] != null && v[i].getNome() == (v1)) {
                aux = v[i];
            }
        }
        return aux;
    }

    /**
     * This method print the adjacency List
     */
    public void printGrafo() {
        System.out.println();
        for (int i = 0; i < a.length; i++) {
            Adjacencia Aux = a[i];
            if (Aux != null) {
                System.out.println();
            }
            while (Aux != null) {
                System.out.printf("%d ->", Aux.getDado().getNome() + 1);
                Aux = Aux.getProx();
            }

        }
    }

    /**
     * This method will return a String with the representation of graph in
     * adjacency list
     *
     * @return a string with the adjacency list
     */
    public String returnGrafo() {
        String string = null;
        Integer aux;
        System.out.println();
        for (int i = 0; i < a.length; i++) {
            Adjacencia Aux = a[i];
            if (Aux != null) {
                System.out.println();
                string += "\n";
            }
            while (Aux != null) {
                System.out.printf("%d ->", Aux.getDado().getNome() + 1);
                aux = Aux.getDado().getNome() + 1;
                string += (aux.toString() + "->");
                Aux = Aux.getProx();
            }

        }
        return string;
    }

    /**
     * This method return the number of elements that a vertex have in his
     * adjacency list including vertex own
     *
     * @param i vertice to be sought
     * @return the number of elements in the adjacency list
     */
    public int matrizNumero(int i) {
        Adjacencia p = this.a[i];
        int distancia = 0;
        while (p != null) {
            distancia += 1;
            p = p.getProx();
        }
        return distancia;

    }

    /**
     *
     * @return a vertex vector this graph.
     */
    public Vertice[] getV() {
        return v;
    }

    /**
     * set a vertex vector this graph.
     *
     * @param v vertex vector to be replaced
     */
    public void setV(Vertice[] v) {
        this.v = v;
    }

    /**
     *
     * @return a adjacency vector to this graph.
     */
    public Adjacencia[] getA() {
        return a;
    }

    /**
     * set a Adjacency vector to this graph.
     *
     * @param a adjacency vector to be replaced
     */
    public void setA(Adjacencia[] a) {
        this.a = a;
    }

    /**
     *
     * @return total of vertices to this graph.
     */
    public int getN() {
        return n;
    }

    /**
     *
     * @return total of edges to this graph.
     */
    public int getM() {
        return m;
    }

}
